home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 134_01 / corodoc.nro < prev    next >
Text File  |  1985-08-19  |  24KB  |  617 lines
  1. .pl 66
  2. .rm 65
  3. .m1 4
  4. .m2 2
  5. .m3 2
  6. .m4 4
  7. .he 'BDS C Coroutine Package''Introduction'
  8. .fo '28 May 1983'-#-'K. B. Kenny'
  9. .ls 1
  10. .ce 3
  11. Coroutine Package for BDS C
  12. by
  13. Kevin B. Kenny
  14. .sp 2
  15. .ul 1
  16. Acknowledgements.
  17. .sp
  18. .ti +5
  19. The BDS 'C' coroutine package is based on one developed at the University of
  20. Waterloo for the programming language 'B' by I. D. Allen.  The author
  21. is also indebted to Peter Fraser, who explained the Waterloo implementation
  22. and provided much good advice for the 'C' version.
  23. .sp 2
  24. .ul 1
  25. 1. Introduction: What are coroutines?
  26. .sp
  27. .ti +5
  28. Every programmer is familiar with the concept of subroutines; portions
  29. of a program that, in effect, provide extensions to the hardware and
  30. allow the programmer to think of complex tasks as sequences of simpler
  31. ones.  While this way of thinking about subroutines is enormously useful,
  32. another view is possible: a main program and its subroutines can be seen
  33. as a team of actors, each with its own job to do.  When the main program
  34. has a task that some subroutine performs, it asks that subroutine for service;
  35. when the subroutine finishes its job, it exits to the main program.
  36. .sp
  37. .ti +5
  38. When a very complex subroutine is written, it is difficult to see it as
  39. simply performing a service for the main program; it might be equally valid
  40. to say that when the subroutine exits to the main program, it is asking
  41. the main program to perform a service for it.  The main program does its
  42. duty, then returns to the subroutine for further orders.
  43. .sp
  44. .ti +5
  45. Consider, for instance, a program which has very complicated operations
  46. to perform on an input stream, eventually producing an output stream.
  47. If the input routine is very complicated, we are tempted to make it the
  48. "main program" and generate the output stream by calling an "output
  49. subroutine".  If, on the other hand, the output procedure is complex,
  50. we are tempted to make
  51. .ul 1
  52. it
  53. the "main program," retrieving its data from the "input subroutine."
  54. What do we do when they are both complicated procedures and neither one
  55. can conveniently be made into a subroutine?
  56. .sp
  57. .ti +5
  58. The solution to this problem is to use
  59. .ul 1
  60. coroutines.
  61. Coroutines are components of a program which are like subroutines in that
  62. they are called from outside (although the correct technical term is
  63. that they are
  64. .ul 1
  65. resumed).
  66. Unlike subroutines, however, neither one of them is the "main program."  
  67. Each can call on the other in as many places as necessary; when one needs
  68. a service (from its point of view) it resumes the other one.  Rather than
  69. entering it from the beginning, however, the machine picks up the
  70. resumed coroutine
  71. .ul 1
  72. exactly where it left off.
  73. The second coroutine then continues processing until, from
  74. .ul 1
  75. its
  76. point of view, it needs the services of the first.  It then resumes the
  77. first coroutine, which is entered where it left off processing.
  78. .sp
  79. .ti +5
  80. To each of the coroutines, then, the other appears as a subroutine.  The
  81. first resumes the second, and the second returns to the first.  This
  82. is the fundamental difference between subroutines and coroutines:  while
  83. a subroutine is always entered at the beginning, a coroutine is always
  84. entered at the point where it left off.
  85. .he 'BDS C Coroutine Package''Rationale'
  86. .sp 3
  87. .ul 1
  88. 2. Rationale: Why use coroutines?
  89. .sp
  90. .ti +5
  91. It is difficult to come up with a simple example of the use of coroutines,
  92. since they are most useful in interfacing two or more complicated tasks.
  93. Generally, if one of the tasks is fairly simple, it is easier to implement
  94. as a subroutine; making a coroutine of it seems contrived.
  95. .sp
  96. .ti +5
  97. The most common uses of coroutines in practice arise either in terms of
  98. multi-pass algorithms or in simulation.  Multi-pass algorithms can use
  99. coroutines to implement the passes, with each resuming the next when it
  100. has output to be processed by the next pass and resuming the prior pass when
  101. input is required.
  102. Simulations can use coroutines to act like independent processes; for instance,
  103. a simulation of a machine shop might use one coroutine to represent each
  104. machine and pass the simulated workpiece around by having these coroutines
  105. resume one another.
  106. .sp
  107. .ti +5
  108. The first of these, the multipass algorithm, is probably more familiar to
  109. C programmers, since Unix pipelines operate this way.  When the user enters
  110. a command like
  111. .sp
  112. .ti +10
  113. .bo
  114. foo | bar | zot
  115. .sp
  116. the system sets up three coroutines, corresponding to the commands "foo,"
  117. "bar," and "zot."
  118. It then enters the "zot" coroutine to begin the processing.
  119. .sp
  120. .ti +5
  121. Things proceed normally until the first time "zot" needs a character from the
  122. standard input stream.  When it does, it calls "getchar" as usual; "getchar"
  123. sees that "zot" has a predecessor in the pipeline.  Rather than reading the
  124. character from the terminal or some file, it resumes "bar" to get the
  125. character.
  126. .sp
  127. .ti +5
  128. Now "bar" starts running, and eventually needs an input character itself.  When
  129. it does, it calls "getchar," who sees that "bar" isn't the first command in the
  130. pipeline either.  As before, it resumes the preceding coroutine, "foo."
  131. "Foo" runs normally, and since it is the first coroutine in the pipe, its calls
  132. to "getchar" cause input from the standard input stream.
  133. .sp
  134. .ti +5
  135. Eventually, "foo" has some output to place on the output stream.  It calls
  136. "putchar," who sees that "foo" isn't the last command in the pipeline.  Instead
  137. of writing the character somewhere, "putchar" resumes the "bar" coroutine,
  138. passing the character to it.  Since "bar" left off processing in "getchar"
  139. where it resumed "foo", it is in just the right state to pick up the character
  140. and continue processing, exactly as if it had been the first command in
  141. the pipeline and got the character from the input stream.
  142. .sp
  143. .ti +5
  144. "Foo" and "bar" continue passing and receiving characters until "bar" has
  145. output to the output stream.  As with "foo", it calls "putchar," who sees
  146. that "bar" isn't the last command in the pipe, either.  It then resumes
  147. "zot", who has been waiting all this time for its first input character.
  148. "Zot" is, of course, still in "getchar;" he picks up the character which
  149. "bar" gave to "putchar" and continues processing.  Since "zot" is the
  150. last coroutine in the pipeline, its calls to "putchar" go on the standard
  151. output stream.
  152. .sp
  153. .ti +5
  154. The disc for the coroutine package contains a sample program organized as
  155. a Unix-style pipeline, in the file "retab.c".  "Retab" consists of the two
  156. programs "entab" and "detab" from
  157. .ul 1
  158. Software Tools,
  159. connected together in the sequence
  160. .sp
  161. .ti +10
  162. .bo
  163. detab | entab
  164. .sp
  165. so that the combination will convert the tabs in its input file to spaces,
  166. and then reconvert them to tabs, possibly at a different set of tab stops.
  167. .sp 3
  168. .he 'BDS C Coroutine Package''Functions Available'
  169. .ul 1
  170. 3. Functions Available in the Coroutine Package.
  171. .sp
  172. .ti +5
  173. The most basic functions available in the coroutine package are C_CREATE,
  174. which creates a coroutine; C_RESUME, which passes control to another coroutine,
  175. and C_DESTROY, which destroys a coroutine.  All of these primitives operate
  176. on a dynamically-allocated area of memory called the
  177. .ul 1
  178. "function control vector (FCV)."
  179. C_CREATE obtains an area of memory from free storage and initializes it as
  180. an FCV, C_RESUME accepts an FCV and transfers into the associated coroutine,
  181. and C_DESTROY accepts an FCV and recovers the space used.
  182. .sp
  183. .ti +5
  184. While these functions are sufficient to implement any application involving
  185. coroutines, the BDS C package supplies several additional primitives to make
  186. certain jobs somewhat easier.
  187. .sp
  188. .ti +5
  189. First, each coroutine has one word of user-specified information in its FCV.
  190. This word, which is set by C_CREATE, can be examined by C_GETINFO and
  191. modified by C_SETINFO.  Normally this word will be a pointer to a structure
  192. containing static storage for the coroutine to use.  For instance, if
  193. the coroutine is modelling a server in a queueing network, the area might
  194. contain head and tail pointers for the queue of transactions waiting